package three;
import java.util.*;

public class A060 {
    public static void main(String[] args) {

        //List<List<String>> ret = partition("baa");
        System.out.println();
    }
    List<List<String>> ret = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        dfs(s,0);
        return ret;
    }

    public void dfs(String s,int start) { //1、每次从start位置开始截取
        if(start>=s.length()) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i=start;i<s.length();i++) {
            if(isTrue(s,start,i)) {
                //截取的[start,i]是回文串
                //1.记录本次回文
                //2.递归剩余字符串是否可以组成回文
                //3.回溯
                path.add(s.substring(start,i+1));
                dfs(s,i+1);
                path.remove(path.size()-1);
            }
        }
    }

    public boolean isTrue(String s,int start,int end) {
        while(start<end) {
            if(s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }

}
